package demo.DataStrucAndAlgo.Tree;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/3-08-03-17:13
 * @Description：demo.DataStrucAndAlgo.Tree
 */
/*
    顺序存储指的是使用顺序表（数组）存储二叉树。顺序存储只适用于完全二叉树
    只有完全二叉树才可以使用顺序表存储。
    顺序（数组）存储二叉树需要遵循一定规律：
        树对应数组索引从root结点开始从左往右由0到n；
        n索引结点左节点对应数组索引为2*n+1；右节点对应数组索引为2*n+2；对应
        父节点为（n-1）/2
 */
class ArrayTree{
    private int size = 0;

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    private String[] tree = null;

    public String[] getTree() {
        return tree;
    }

    public ArrayTree() {
        this(10);
    }
    public ArrayTree(int size) {
        tree = new String[size];
    }
    public void grow(){
        tree = Arrays.copyOf(tree,(tree.length + tree.length/2));
    }
    public void addData(String data){
        if(size == tree.length){
            grow();
        }
        tree[size++] = data;
    }
    public void delete(String data){
        if(size == 0){
            throw new RuntimeException("当前树为空树！删除失败！");
        }
        int i;
        for (i = 0; i < size; i++) {
            if(tree[i].equals(data)){
                break;
            }
        }
        if(i<size){
            for (int j = i; j < size-1; j++) {
                tree[j] = tree[j+1];
            }
            size--;
        }else{
            System.out.println("你要删除的元素不存在！");
        }
    }
    public void PreOrder(int index){
        System.out.print(tree[index] + " ");
        if(index*2+1<size){
            PreOrder(index*2+1);
        }
        if(index*2 + 2 < size){
            PreOrder(index*2+2);
        }
    }
    public void infixOrder(int index){
        if(index*2+1<size){
            infixOrder(index*2+1);
        }
        System.out.print(tree[index] + " ");
        if(index*2+2<size){
            infixOrder(index*2+2);
        }
    }
    public void PostOrder(int index){
        if(index*2+1<size){
            PostOrder(index*2+1);
        }
        if(index*2+2<size){
            PostOrder(index*2+2);
        }
        System.out.print(tree[index] + " ");
    }
}
public class ArrBinaryTree {
    public static void main(String[] args) {
        ArrayTree trees = new ArrayTree(3);
        trees.addData("A");
        trees.addData("B");
        trees.addData("C");
        trees.addData("D");
        trees.addData("E");
        trees.addData("F");
        trees.addData("G");
        trees.addData("H");
        trees.addData("I");

        trees.PreOrder(0);
        System.out.println("------------------------------");
        trees.infixOrder(0);
        System.out.println("-------------------------");
        trees.PostOrder(0);
        System.out.println("-------------------------");

        System.out.println("当前存储tree的数组大小为：" + trees.getTree().length);

        trees.delete("D");

        trees.PreOrder(0);
        System.out.println("-------------------------");
        trees.infixOrder(0);
        System.out.println("-------------------------");
        trees.PostOrder(0);
        System.out.println("-------------------------");
    }

}
